package com.example.graph;

import java.util.*;

/**
 * 给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，
 * 其中 edges[i] = [a, b] 表示连接节点 a 和 b的一条无向边，且该边遍历成功的概率为 succProb[i] 。
 * 指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
 * 如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。
 * <p>
 * 示例 1：
 * 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
 * 输出：0.25000
 * 解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25
 * <p>
 * 示例 2：
 * 输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
 * 输出：0.30000
 * <p>
 * 示例 3：
 * 输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
 * 输出：0.00000
 * 解释：节点 0 和 节点 2 之间不存在路径
 * <p>
 * 提示：
 * 2 <= n <= 10^4
 * 0 <= start, end < n
 * start != end
 * 0 <= a, b < n
 * a != b
 * 0 <= succProb.length == edges.length <= 2*10^4
 * 0 <= succProb[i] <= 1
 * 每两个节点之间最多有一条边
 */
public class Leetcode1514_MaxProbability {
    public static void main(String[] args) {
        int n = 3;
        int[][] edges = {{0, 1}, {1, 2}, {0, 2}};
        double[] succProb = {0.5, 0.5, 0.3};
        int start = 0, end = 2;
        double prob = new Solution().maxProbability(n, edges, succProb, start, end);
        System.out.println(prob);


    }

    static class Solution {
        public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
            return maxProbability1(n, edges, succProb, start, end);
        }

        /**
         * 迪杰斯特拉算法(堆优化其实只是省掉了每次在邻接点中寻找最值的过程)
         *
         * @param n
         * @param edges
         * @param succProb
         * @param start
         * @param end
         * @return
         */
        public double maxProbability1(int n, int[][] edges, double[] succProb, int start, int end) {
            // 1. 构建邻接表
            Map<Integer, List<Pair>> adj = new HashMap<>();
            for (int i = 0; i < edges.length; i++) {
                adj.computeIfAbsent(edges[i][0], key -> new ArrayList<>())
                        .add(new Pair(edges[i][1], succProb[i]));

                adj.computeIfAbsent(edges[i][1], key -> new ArrayList<>())
                        .add(new Pair(edges[i][0], succProb[i]));
            }

//            Set<Map.Entry<Integer, List<Pair>>> entries = adj.entrySet();
//            Iterator<Map.Entry<Integer, List<Pair>>> iterator = entries.iterator();
//            while (iterator.hasNext()) {
//                Map.Entry<Integer, List<Pair>> entry = iterator.next();
//                System.out.print(entry.getKey() + " -->");
//                entry.getValue().forEach(e -> {
//                    System.out.print(e + ",");
//                });
//                System.out.println();
//            }


            double[] prob = new double[n]; // 从start到达索引为i的顶点的最大概率为prob[i]
            Queue<Pair> maxHeap = new PriorityQueue<>();

            maxHeap.offer(new Pair(start, 1.0)); // 将开始节点放入到堆中
            prob[start] = 1.0;

            while (!maxHeap.isEmpty()) {
                Pair pair = maxHeap.poll();
                double pr = pair.prob;
                int node = pair.node;

                if (pr < prob[node]) { // 如果到达node的概率值比当前的要小，则直接跳过循环
                    continue;
                }

                if (adj.containsKey(node)) {
                    for (Pair p : adj.get(node)) { // 拿到节点的邻接点(BFS)
                        double prNext = p.prob;
                        int nodeNext = p.node;
                        // prob[node] * prNext 表示通过node节点到达node的邻接点nodeNext的概率
                        if (prob[nodeNext] < prob[node] * prNext) { // 满足到达邻接点的概率比之前的要大就更新
                            prob[nodeNext] = prob[node] * prNext;
                            maxHeap.offer(new Pair(nodeNext, prob[nodeNext]));
                        }
                    }
                }
            }
//            for (double v : prob) {
//                System.out.println(v);
//            }
            return prob[end];
        }

        class Pair implements Comparable<Pair> {
            private int node;
            private double prob;

            public Pair(int node, double prob) {
                this.node = node;
                this.prob = prob;
            }

            /**
             * 先按照pro从大到小进行排序，如果prob相同，则按照node从小到大进行排序
             *
             * @param other
             * @return
             */
            @Override
            public int compareTo(Pair other) {
//                if (this.prob == other.prob) {
//                    return this.node - other.node;
//                } else {
//                    return this.prob - other.prob > 0 ? -1 : 1;
//                }

                if (this.prob == other.prob) {
                    return this.node - other.node;
                } else {
                    return this.prob - other.prob > 0 ? -1 : 1;
                }
            }


            @Override
            public String toString() {
                return "Pair{" +
                        "node=" + node +
                        ", prob=" + prob +
                        '}';
            }
        }
    }
}
